#ifndef __PRORITY_QUEUE_H__
#define __PRORITY_QUEUE_H__

namespace Aurora
{
    template<class T>
    struct less
    {
        bool operator()(const T& x,const T& y)
        {
            return x < y;
        }
    };
    template<class T>
    struct greater
    {
        bool operator()(const T& x,const T& y)
        {
            return x > y;
        }
    };
    template <class T,class Container = std::vector<T>,class Compare = Aurora::less<T>>
    class priority_queue
    {
    public:
        //priority_queue() = default;
        //迭代器区间构造
        template<class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
            :_con(first,last)
        {
            for(int i = (size()-2)/2;i >= 0;i--)
            {
                AdjestDown(i);
            }
        }
        void AdjestUp(size_t child)
        {
            //计算父节点
            size_t parent = (child - 1)/2;
            while(child)
            {
                //小堆 > 大堆 <
                if(_cmp(_con[parent] , _con[child]))
                {
                    std::swap(_con[parent] , _con[child]);
                    child = parent;
                    parent = (child - 1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void AdjestDown(size_t parent)
        {
            //计算子节点
            size_t child = parent * 2 + 1;
            while(child < size())
            {
                //找大 >  找小 <
                if(child + 1 < size() && _cmp( _con[child] , _con[child + 1]))
                {
                    child++;
                }
                //小堆 > 大堆 <
                if(_cmp(_con[parent] , _con[child]))
                {
                    std::swap(_con[parent],_con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else 
                {
                    break;
                }
            }
        }
        void push(const T& data)
        {
            _con.push_back(data);
            //调用向上调整算法建堆
            AdjestUp(size()-1);
        }
        void pop()
        {
            //堆顶数据和堆尾数据交换
            std::swap(_con[0],_con[size()-1]);
            //出数据
            _con.pop_back();
            //向下调整算法建堆小堆
            AdjestDown(0);
        }
        void Debug()
        {
            for(const auto &e : _con)
            {
                std::cout << e << " ";
            }
            std::cout << std::endl;
        }
        size_t size() const
        {
            return _con.size();
        }
        bool empty() const
        {
            return _con.empty();
        }
        const T& top() const
        {
            return _con.front();
        }
    private:
        Container _con;
        Compare _cmp;
    };
}

#endif